package leetCode.solution;

import com.alibaba.fastjson.JSON;

public class Solution34 {
	public static void main(String[] args) {
		System.out.println(JSON.toJSONString(new Solution34().searchRange(new int[] {1,2,3,3,3,3,4,5,9},3)));
	}
	
	public int[] searchRange(int[] nums, int target) {
		if(nums==null || nums.length==0) {
			return new int[] {-1,-1};
		}
		return binSearch(nums, 0, nums.length-1, target);
    }
	
	private int[] binSearch(int[] nums, int l, int r, int target) {
		if(l==r) {
			return nums[l]==target?new int[] {l,l}:new int[] {-1,-1};
		}
		if(l>r) {
			return new int[] {-1,-1};
		}
//		if(l+1==r) {
//			return new int[] {nums[l]==target?l:nums[r]==target?r:-1,nums[r]==target?r:nums[l]==target?l:-1};
//		}
		int mid = l + ((r-l)>>1);
		if(nums[mid]<target) {
			return binSearch(nums, mid+1, r, target);
		}
		if(nums[mid]==target) {
			int [] leftResult = binSearch(nums, l, mid-1, target);
			int [] rightResult = binSearch(nums, mid+1, r, target);
			return new int[] { leftResult[0]==-1?mid:leftResult[0], rightResult[1]==-1?mid:rightResult[1]} ;
		}
		if(nums[mid]>target) {
			return binSearch(nums, l, mid-1, target);
		}
		return new int[] {-1,-1}; 
	}
}